// https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    void dfs(vector<vector<int>>& ans, vector<int>& candidates, int target, int sum, vector<int>& comb, int idx) {
        if (idx == candidates.size()) return;

        if (sum >= target) {
            if (sum == target) {
                ans.push_back(comb);
            }
            return;
        }

        if (sum + candidates[idx] <= target) {
            comb.push_back(candidates[idx]);
            sum += candidates[idx];
            dfs(ans, candidates, target, sum, comb, idx);
            comb.pop_back();
            sum -= candidates[idx];
        }
        dfs(ans, candidates, target, sum, comb, idx + 1);
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> comb;
        dfs(ans, candidates, target, 0, comb, 0);
        return ans;
    }
};